This invention relates to management of free addresses, and particularly to free address management employing a hierarchical tree for reduced latency with minimal increased external memory.
In the synthesis of VLSI designs for storage systems and for communication devices, it is often necessary to make use of a manager of free addresses in an external memory storage. Memory access, such as for read and write memory operations, can usually be accomplished with arbitrarily chosen memory addresses in one time unit (e.g., one clock cycle). It is also desired that other operations, such as initialization and reset operations be accomplished in small time periods, most preferably in one time unit (one clock cycle). Such a situation arises when managing free indices in fast flexible search engines, such as described in application Ser. Nos. 09/679,209 and 09/679,313 both filed Oct. 4, 2000 by Andreev et al. for xe2x80x9cFast Flexible Search Engine for Longest Prefix Matchxe2x80x9d and for xe2x80x9cFlexible Search Engine Having Sorted Binary Tree for Perfect Matchxe2x80x9d and assigned to the same assignee as the present invention.
Previously, free address management techniques required unsatisfactory timing requirements for allocation and freeing operations, excessive time for initialization and reset operations, and/or excessive external memory consumption.
A memory manager manages read and write operations of an external memory. A set of memory addresses, herein called xe2x80x9cindicesxe2x80x9d, I={0,1, . . . n} contains subsets of Free indices and Taken (also called xe2x80x9callocatedxe2x80x9d) indices. An ALLOC command will output a Free index (if any) from set I thereby allocating the index, and a FREE command will change a Taken index to a Free index. RESET and INIT commands will reset and initialize the memory.
Prior memory managers managed indices either as a characteristic array of all (Free and Taken) indices of the set I, or by managing the stack or list of only the Free indices.
A memory manager managing indices as a characteristic array of Free and Taken indices requires an external memory having a capacity of n bits, where n is the total number of indices to be distributed. Hence, external memory consumption is only 1 bit per index. The worst-case latency, in clock cycles, of the manager (when looking for a Free index) is approximately n/2k, where 2k is the word length in bits used in the external memory (typically, k=16, 32 or 64). A reset operation also requires approximately n/2k clock cycles. This management technique offers the advantage of minimal memory requirements of only n bits. However, where the number n of indices is large, for example where n is greater than 1024, the latency and reset requirements are unacceptable.
A memory manager managing a stack or list of only Free indices requires an external memory having a capacity of nxc2x7log2n bits, with each index requiring log2n bits. The worst-case latency of the manager (when looking for a Free index) is only one clock cycle (since every index in the stack or list is, by definition, a Free index). However, a worst-case reset operation requires approximately n clock cycles. While the latency is quite satisfactory at one time unit (one clock cycle), memory consumption (nxc2x7log2n bits) and reset time (n cycles) are unsatisfactory.
Thus, in one way or in another, these prior techniques for managing free addresses (or indices) are ineffective for practical implementation where a fast running module interacts with an external memory. The present invention provides a solution to these and other problems, and offers advantages over the prior art.
In one embodiment, a storage memory contains a memory manager for managing allocation of addresses in the memory. The memory manager is structured, as a hierarchical tree having a top vertex, a bottom level and at least one intermediate level between the top vertex and bottom level. The bottom level contains a plurality of bottom vertices each containing a plurality of representations of a Free or Taken status of respective addresses in the memory. Each intermediate level contains at least one hierarchy vertex containing a plurality of labels. Each label is associated with a child vertex and defines whether or not a path that includes the respective child vertex ends in a respective bottom level vertex containing at least one Free representation.
Another embodiment of the invention is a process of managing free addresses in a memory. A hierarchical tree contains a plurality of vertices arranged in a plurality of levels such that a bottom level contains a plurality of bottom vertices each containing a plurality of representations of a Free or Taken status of respective addresses in the memory and at least one intermediate level contains at least one hierarchy vertex containing a plurality of labels defining whether or not a path that includes the respective child vertex ends in a respective bottom level vertex containing at least one Free representation. A memory command is input to the tree, and the representation of the status of an address in a bottom level vertex is changed based on the command.
In some embodiments, if the command is an allocate command, a search is performed through the tree, starting at the top vertex, to locate a Fee address in a vertex in the bottom level. The status of that address is changed to Taken and labels are changed in vertices in the intermediate level(s) as appropriate, depending on the status of other representations in that bottom level vertex.
In other embodiments, if the command is a Free command to set free a designated address, the representation in the bottom level vertex associated with that address is changed to Free and labels are changed in vertices in intermediate level(s) as appropriate, depending on the status of other representations in that bottom level vertex.
In other embodiments, the invention is manifest in computer readable code that is stored on a computer readable medium to cause the computer to perform the processes of the invention. The medium may be a transportable medium, such as a floppy disc medium, and includes code causing the computer to structure the tree in the memory containing the addresses.